package main.Q701_800;

import java.util.*;

public class Q751_760 {
    public static void main(String[] args) {
        System.out.println("Question751：");
        System.out.println("Question752：打开转盘锁");
        String[] deadends={"0201","0101","0102","1212","2002"};
        System.out.println(new Question752().openLock(deadends,"0202"));
        System.out.println("Question753：");
        System.out.println("Question754：");
        System.out.println("Question755：");
        System.out.println("Question756：");
        System.out.println("Question757：");
        System.out.println("Question758：");
        System.out.println("Question759：");
        System.out.println("Question760：");
    }
}

class Question752{
    public int openLock(String[] deadends, String target) {
        if ("0000".equals(target)) return 0;
        Set<String> dead = new HashSet<String>();
        for (String deadend : deadends)
            dead.add(deadend);
        if (dead.contains("0000")) return -1;
        int step = 0;
        Queue<String> queue = new LinkedList<String>();
        queue.offer("0000");
        Set<String> seen = new HashSet<String>();
        seen.add("0000");
        while (!queue.isEmpty()) {
            ++step;
            int size = queue.size();
            for (int i = 0; i < size; ++i) {
                String status = queue.poll();
                for (String nextStatus : get(status)) {
                    if (!seen.contains(nextStatus) && !dead.contains(nextStatus)) {
                        if (nextStatus.equals(target)) {
                            return step;
                        }
                        queue.offer(nextStatus);
                        seen.add(nextStatus);
                    }
                }
            }
        }
        return -1;
    }
    public char numPrev(char x) {return x == '0' ? '9' : (char) (x - 1);}
    public char numSucc(char x) {return x == '9' ? '0' : (char) (x + 1);}
    // 枚举 status 通过一次旋转得到的数字
    public List<String> get(String status) {
        List<String> ret = new ArrayList<String>();
        char[] array = status.toCharArray();
        for (int i = 0; i < 4; ++i) {
            char num = array[i];
            array[i] = numPrev(num);
            ret.add(new String(array));
            array[i] = numSucc(num);
            ret.add(new String(array));
            array[i] = num;
        }
        return ret;
    }
}